
// 213. 打家劫舍II
class Solution {
public:
    int rob(vector<int>& nums) {
        // 将类型进行分类: 1. 第一个房屋偷  2. 第一个房屋不偷
        int n = nums.size();
        function<int(int,int)> Rob = [&](int left , int right)
        {
            if(left > right) return 0;
            vector<int> f(n + 1),g(n + 1);      //f表示当前位置抢劫,可以获得的最大利润  g表示当前位置不抢, 可以获得的最大利润
            f[left] = nums[left];

            for(int i = left + 1; i <= right ; i++)
            {
                f[i] = g[i-1] + nums[i];
                g[i] = max(g[i-1],f[i-1]); 
            }
            return max(f[right],g[right]);
        };

        return max(Rob(2,n-2) + nums[0],Rob(1,n-1));
    }
};